package leetcode_300;


import java.util.HashMap;
import java.util.Map;
import java.util.Set;


/**
 *@author 周杨
 *AddandSearchWord_211 构造字典树提供插入 搜索功能 其中.能替换所有字符
 *describe:用字典树实现 AC 26%
 *2018年6月14日 下午7:04:47
 */
public class AddandSearchWord_211 {
	private TrieNode root;
	String s;

	class TrieNode {
	    boolean isWord;
	    HashMap<Character, TrieNode> nexts;

	    public TrieNode() {
	        nexts = new HashMap<Character, TrieNode>();
	    }
	}
	public static void main(String[] args) {
		AddandSearchWord_211 test=new AddandSearchWord_211();
		test.addWord("bad");
		System.out.println(test.search("bad"));

	}
	
	/** Initialize your data structure here. */
    public AddandSearchWord_211() {
    	root = new TrieNode();
    }
    
    /** Inserts a word into the trie. */
    public void addWord(String word) {
    	char[] s = word.toCharArray();

        TrieNode p = root;
        int i = 0, n = s.length;

        // traverse existing
        while (i < n) {
            TrieNode next = p.nexts.get(s[i]);
            if (next != null) {
                p = next;
                i ++;
            } else {
                break;
            }
        }
        
        // append new nodes
        while (i < n) {
            TrieNode newTrie = new TrieNode();
            p.nexts.put(s[i], newTrie);
            p = newTrie;
            i ++;
        }

        // set word end
        p.isWord = true;
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
    	this.s=word;
    	TrieNode p = root;
    	return help(p,0);
    }
    
    public boolean help(TrieNode p,int index) {
    	char now=s.charAt(index);
    	if(now=='.') {
    		Set<Map.Entry<Character, TrieNode>> set=p.nexts.entrySet();
    		if(set.size()==0) {
    			return false;
    		}
    		else {
    			for(Map.Entry<Character, TrieNode> scan :set) {
    				if(index==s.length()-1) {
        				if(scan.getValue().isWord)
        					return true;
        				else
        					continue;
        			}
        			else
        				if(help(scan.getValue(),index+1))
        					return true;
    			}
    			return false;
    		}
    	}
    	else {
    		TrieNode nowNode=p.nexts.get(now);
    		if(nowNode==null)
    			return false;
    		else {
    			if(index==s.length()-1)
    				if(nowNode.isWord)
    					return true;
    				else
    					return false;
    			return help(nowNode,index+1);
    		}
    	}
    }
    
    

}
